package 二0年4月;
/*
* 设计一个算法，算出 n 阶乘有多少个尾随零。

示例 1:

输入: 3
输出: 0
解释: 3! = 6, 尾数中没有零。  3*2*1=6
示例 2:

输入: 5
输出: 1
解释: 5! = 120, 尾数中有 1 个零.  5*4*3*2*1=120

思路：在数的阶乘中，如果出现尾数为0，则证明有因子5和2的存在，

    只有包括5的阶乘才能出现0，所以只要计算阶乘是5的倍数的个数，
比如,、25的倍数的个数（包含两个5）、125的倍数的个数（包含3个5）......

* */
public class InterView1605 {
    public int trailingZeroes(int n) {
        int sum=0;
        while (n!=0){
            sum+=n/5; //每次判断n中有多少个5，就加上。
            n=n/5;
        }
        return sum;
    }

    //递归的实现方式
    int helper(int n) { // n!中有多少个5
        if (n < 5) return 0;
        return helper(n / 5) + n / 5;
        // 5*x <= n; 于是5*1*a1*5*2*a1*...*5*x <= n, 即5*5*..*5*a1*...*an*1*2*...*x <= n
        // 于是n!中5的个数 = (x + x!中5出现的个数)
    }

}
